package com.lw.leetcode.sort.c;

import com.lw.test.util.Utils;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 164. 最大间距
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/21 9:52
 */
public class MaximumGap {

    public static void main(String[] args) {
        MaximumGap test = new MaximumGap();

        // 3
//        int[] arr = {3, 6, 9, 1};

        // 0
//        int[] arr = {10};

        //
        int[] arr = Utils.getArr(10000, 0, 1000000000);

        int i = test.maximumGap(arr);
        System.out.println(i);
    }

    public int maximumGap(int[] nums) {
        int length = nums.length;
        int[][] items = new int[10][length];
        int[] count = new int[10];
        long st = 1;
        long end = 10;
        for (int i = 0; i < 10; i++) {
            for (int a : nums) {
                int v = (int) (a % end / st);
                items[v][count[v]] = a;
                count[v]++;
            }
            st *= 10;
            end *= 10;
            int index = 0;
            for (int j = 0; j < 10; j++) {
                int[] item = items[j];
                int l = count[j];
                for (int k = 0; k < l; k++) {
                    nums[index++] = item[k];
                }
            }
            Arrays.fill(count, 0);
        }
        int max = 0;
        for (int i = 1; i < length; i++) {
            max = Math.max(max, nums[i] - nums[i - 1]);
        }
        return max;
    }

}
